package com.congee02;

import java.util.*;

public class MinWindow_Enum_O1 {

    public String minWindow(String s, String t) {

        char[] cs = s.toCharArray();

        int[] needed = need(t);

        int needTotal = t.length();

        // l = r = 0
        if (sub(needed, cs[0])) {
            needTotal --;
        }
        if (needTotal == 0) {
            return cs[0] + "";
        }

        int minLen = Integer.MAX_VALUE;
        int ansL = -1;
        int ansR = -1;
        int l = 0;
        for (int r = 1 ; r < cs.length ; r ++ ) {
            if (sub(needed, cs[r])) {
                needTotal --;
            }
            System.out.println("l=" + l + ", r=" + r + ", needTotal=" + needTotal);
            while (needTotal == 0) {
                int len = r - l + 1;
                if (len < minLen) {
                    minLen = len;
                    ansL = l;
                    ansR = r;
                }
                if (add(needed, cs[l ++])) {
                    needTotal ++;
                }
            }
        }


        return ansL == -1 ? "" : s.substring(ansL, ansR + 1);
    }

    private final int NO_NEED = 100001;
    private int[] need(String t) {
        char[] cs = t.toCharArray();
        int[] ans = new int[256];
        Arrays.fill(ans, NO_NEED);
        for (char x : cs) {
            if (ans[x] == NO_NEED) {
                ans[x] = 1;
            } else {
                ans[x] ++;
            }
        }
        return ans;
    }

    // 减少了一个需求
    private boolean sub(int[] map, char x) {
        if (map[x] == NO_NEED) {
            return false;
        }
        map[x] --;
        return map[x] >= 0;
    }

    // 新增了一个需求
    private boolean add(int[] map, char x) {
        if (map[x] == NO_NEED) {
            return false;
        }
        map[x] ++;
        return map[x] >= 1;
    }


}
